<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">

<head>
  <title>Express Ports</title>
  <meta http-equiv="content-type" content="application/xhtml+xml; charset=UTF-8" />
  <link rel="stylesheet" type="text/css" href="style/html.css" />
  <link rel="stylesheet" type="text/css" href="style/svg.css" />
  <svg xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:svg="http://www.w3.org/2000/svg"
    width="306pt" height="82pt" viewBox="-5 -1 306 82" class="right"
  >
  <defs>
    <marker id="arrow-end" viewBox="0 -2 4 4" refX="4" refY="0" markerUnits="strokeWidth" orient="auto" markerWidth="4" markerHeight="4">
      <polyline points="0,-2 4,0 0,2" fill="black"/>
    </marker>
    <marker id="req-end" viewBox="0 -2 11 4" refX="11" refY="0" markerUnits="strokeWidth" orient="auto" markerWidth="11" markerHeight="4">
      <polyline points="0,-2 5,0 0,2" class="req-marker"/>
    </marker>
    <circle id="state"     class="state" cx="0" cy="0" r="10"/>
    <circle id="state-dep" class="state dep" cx="0" cy="0" r="10"/>
    <circle id="state-cpu" class="state cpu" cx="0" cy="0" r="10"/>
    <circle id="state-io"  class="state io" cx="0" cy="0" r="10"/>
    <circle id="state-net" class="state net" cx="0" cy="0" r="10"/>
    <circle id="state-human" class="state man" cx="0" cy="0" r="10"/>
    <circle id="seq-state"     class="state" cx="0" cy="0" r="6"/>
    <circle id="seq-state-dep" class="state dep" cx="0" cy="0" r="6"/>
    <circle id="seq-state-cpu" class="state cpu" cx="0" cy="0" r="6"/>
    <circle id="seq-state-io"  class="state io" cx="0" cy="0" r="6"/>
    <circle id="seq-state-net" class="state net" cx="0" cy="0" r="6"/>
    <circle id="seq-state-human" class="state man" cx="0" cy="0" r="6"/>
    <g id="state-C"><circle class="state man" cx="0" cy="0" r="10"/><text class="state" y="4">C</text></g>
    <g id="state-D"><circle class="state dep" cx="0" cy="0" r="10"/><text class="state" y="4">D</text></g>
    <g id="state-F"><circle class="state net" cx="0" cy="0" r="10"/><text class="state" y="4">F</text></g>
    <g id="state-I"><circle class="state cpu" cx="0" cy="0" r="10"/><text class="state" y="4">I</text></g>
    <g id="state-c"><circle class="state man" cx="0" cy="0" r="6"/><text class="seq-state" y="3">C</text></g>
    <g id="state-d"><circle class="state dep" cx="0" cy="0" r="6"/><text class="seq-state" y="3">D</text></g>
    <g id="state-f"><circle class="state net" cx="0" cy="0" r="6"/><text class="seq-state" y="3">F</text></g>
    <g id="state-i"><circle class="state cpu" cx="0" cy="0" r="6"/><text class="seq-state" y="3">I</text></g>
    <rect id="desc-cpu" class="desc cpu" width="100" height="10"/>
    <rect id="desc-io" class="desc io" width="100" height="10"/>
    <rect id="desc-net" class="desc net" width="100" height="10"/>
    <rect id="desc-human" class="desc man" width="100" height="10"/>
    <rect id="port" x="-30" y="-11" width="60" height="16" rx="5" ry="5"/>
    <rect id="port-config" x="-30" y="-11" width="60" height="16" rx="5" ry="5"/>
    <g id="port-phases">
        <g transform="translate(10,10)">
            <line x1="-15" x2="-10" class="trans"/><use xlink:href="#state-D"/>
        </g>
        <g transform="translate(50,10)">
            <line x1="-30" x2="-10" class="trans"/><use xlink:href="#state-F"/>
        </g>
        <g transform="translate(90,10)">
            <line x1="-30" x2="-10" class="trans"/><use xlink:href="#state-I"/>
        </g>
    </g>
    <g id="port-phases-with-config">
        <g transform="translate(10,10)">
            <line x1="-15" x2="-10" class="trans"/><use xlink:href="#state-C"/>
        </g>
        <g transform="translate(50,10)">
            <line x1="-30" x2="-10" class="trans"/><use xlink:href="#state-D"/>
        </g>
        <g transform="translate(90,10)">
            <line x1="-30" x2="-10" class="trans"/><use xlink:href="#state-F"/>
        </g>
        <g transform="translate(130,10)">
            <line x1="-30" x2="-10" class="trans"/><use xlink:href="#state-I"/>
        </g>
    </g>
    <g id="seq-port">
        <line x1="10" x2="30" class="req"/>
        <use x="-10" xlink:href="#state-d"/>
        <use x="10"  xlink:href="#state-f"/>
        <use x="30"  xlink:href="#state-i"/>
    </g>
    <g id="seq-port-config">
        <line x1="-30" x2="-10" class="req"/>
        <line x1="10"  x2="30"  class="req"/>
        <use transform="translate(-30,0)" xlink:href="#state-c"/>
        <use transform="translate(-10,0)" xlink:href="#state-d"/>
        <use transform="translate(10,0)"  xlink:href="#state-f"/>
        <use transform="translate(30,0)"  xlink:href="#state-i"/>
    </g>
    <g id="par-port">
        <use xlink:href="#port" style="opacity: 0.3;"/>
        <line x1="-10" x2="10" y1="10" y2="10" class="req"/>
        <line x1="10"  x2="30" y1="10" y2="10" class="req"/>
        <use transform="translate(-10,10)" xlink:href="#state-d"/>
        <use transform="translate(10,10)"  xlink:href="#state-f"/>
        <use transform="translate(30,10)"  xlink:href="#state-i"/>
    </g>
    <g id="par-port-config">
        <use xlink:href="#port-config" style="opacity: 0.3;"/>
        <line x1="-30" x2="-10" y1="10" y2="10" class="req"/>
        <line x1="-10" x2="10"  y1="10" y2="10" class="req"/>
        <line x1="10"  x2="30"  y1="10" y2="10" class="req"/>
        <use transform="translate(-30,10)" xlink:href="#state-c"/>
        <use transform="translate(-10,10)" xlink:href="#state-d"/>
        <use transform="translate(10,10)"  xlink:href="#state-f"/>
        <use transform="translate(30,10)"  xlink:href="#state-i"/>
    </g>
    <line id="queue-side" x2="80"/>
    <g id="sides"><use xlink:href="#queue-side"/><use y="20" xlink:href="#queue-side"/></g>
    <g id="queue-man"><rect width="80" height="20" class="man"/><use xlink:href="#sides"/></g>
    <g id="queue-dep"><rect width="80" height="20" class="dep"/><use xlink:href="#sides"/></g>
    <g id="queue-net"><rect width="80" height="20" class="net"/><use xlink:href="#sides"/></g>
    <g id="queue-cpu"><rect width="80" height="20" class="cpu"/><use xlink:href="#sides"/></g>
    <g id="thread"><rect x="-15" y="1" width="30" height="8" rx="10" ry="3" class="thread"/><text y="8" class="thread">thread</text></g>
    <polyline id="fat-arrow" points="0,-5 5,-5 5,-7 10,0 5,7 5,5 0,5" class="req-marker"/>
    <g id="threadpool">
        <use xlink:href="#fat-arrow" x="-15" y="20"/>
        <rect width="60" height="40" rx="25" ry="20" class="threadpool"/>
        <use x="30" y="2" xlink:href="#thread"/>
        <use x="30" y="12" xlink:href="#thread"/>
        <text x="30" y="26" class="thread">...</text>
        <use x="30" y="28" xlink:href="#thread"/>
    </g>
  </defs>
  </svg>
</head>

<body>
  <div class="document">
  <h1>Express Ports</h1>
  <small>Tool to optimize freebsd ports/packages operations</small>

  <h2>Table of Contents</h2>
  <ol>
    <li><a href="chapter-1">Intro</a></li>
    <li><a href="chapter-2">Phases of port processing</a></li>
    <li><a href="chapter-3">Port dependencies</a></li>
    <li><a href="chapter-4">System resources</a></li>
    <li><a href="chapter-5">Port decomposition</a></li>
  </ol>

  <h2>Into</h2>
  <ul>
    <li>Port phases, resources</li>
    <li>Sequential processing</li>
    <li>Quasiparallel processing</li>
    <li>Decomposition of graph</li>
    <li>Artificial dependencies</li>
    <li>Submit dependencies</li>
    <li>Paralel graph construction</li>
    <li>Operations on incomplete graph - locality</li>
  </ul>
  <p>
  
  </p>

  <h2>Phases of a single port installation</h2>
  <div class="figure right" title="Port installation processing">
  <svg xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:svg="http://www.w3.org/2000/svg"
    width="306pt" height="82pt" viewBox="-5 -1 306 82" class="right"
  >
  <defs>
    <marker id="arrow-end" viewBox="0 -2 4 4" refX="4" refY="0" markerUnits="strokeWidth" orient="auto" markerWidth="4" markerHeight="4">
      <polyline points="0,-2 4,0 0,2" fill="black"/>
    </marker>
    <circle id="state"     class="state" cx="0" cy="0" r="10"/>
    <circle id="state-cpu" class="state cpu" cx="0" cy="0" r="10"/>
    <circle id="state-io"  class="state io" cx="0" cy="0" r="10"/>
    <circle id="state-net" class="state net" cx="0" cy="0" r="10"/>
    <circle id="state-human" class="state human" cx="0" cy="0" r="10"/>
    <rect id="desc-cpu" class="desc cpu" width="100" height="10"/>
    <rect id="desc-io" class="desc io" width="100" height="10"/>
    <rect id="desc-net" class="desc net" width="100" height="10"/>
    <rect id="desc-human" class="desc human" width="100" height="10"/>
  </defs>

  <!--path d="M 17,14 Q 50,40 83,14" class="trans"/-->
  <line x1="-5" y1="10" x2="1" y2="10" class="trans"/>
  <g transform="translate(10,10)">
    <use xlink:href="#state-human"/><text class="state" y="4">1</text>
    <line x1="10" x2="30" class="trans"/>
  </g>
  <g transform="translate(50,10)">
    <use xlink:href="#state-cpu"/><text class="state" y="4">2</text>
    <line x1="10" x2="30" class="trans"/>
  </g>
  <g transform="translate(90,10)">
    <use xlink:href="#state-net"/><text class="state" y="4">3</text>
    <line x1="10" x2="30" class="trans"/>
  </g>
  <g transform="translate(130,10)">
    <use xlink:href="#state-io"/><text class="state" y="4">4</text>
    <line x1="10" x2="30" class="trans"/>
  </g>
  <g transform="translate(170,10)">
    <use xlink:href="#state-cpu"/><text class="state" y="4">5</text>
    <line x1="10" x2="30" class="trans"/>
  </g>
  <g transform="translate(210,10)">
    <use xlink:href="#state-cpu"/><text class="state" y="4">6</text>
    <line x1="10" x2="30" class="trans"/>
  </g>
  <g transform="translate(250,10)">
    <use xlink:href="#state-io"/><text class="state" y="4">7</text>
    <line x1="10" x2="30" class="trans"/>
  </g>
  <g transform="translate(290,10)">
    <use xlink:href="#state-io"/><text class="state" y="4">8</text>
  </g>

  <text x="199" y="38" class="desc">Resources:</text>
  <g transform="translate(199,40)"><use xlink:href="#desc-cpu"/><text x="2" y="8" class="desc">CPU</text></g>
  <g transform="translate(199,50)"><use xlink:href="#desc-io"/><text x="2" y="8" class="desc">Disk I/O</text></g>
  <g transform="translate(199,60)"><use xlink:href="#desc-net"/><text x="2" y="8" class="desc">Network</text></g>
  <g transform="translate(199,70)"><use xlink:href="#desc-human"/><text x="2" y="8" class="desc">Human interaction</text></g>
  </svg>
  </div>

  <ol>
    <li>Configuration (optional)</li>
    <li>Fetch</li>
    <li>Extract</li>
    <li>Patch</li>
    <li>Configure</li>
    <li>Build</li>
    <li>Install</li>
    <li>Clean</li>
  </ol>

  <div class="phase">
    Get port options:
    <pre class="terminal"># make -V OPTIONS</pre>
    Configure the port:
    <pre class="terminal"># make config</pre>
    Configure the port and it's dependencies:
    <pre class="terminal"># make config-recursive</pre>
    Configure the port only if not yet configured:
    <pre class="terminal"># make do-config</pre>
  </div>
  <h3>Port configuration</h3>
  <p>
  This is a FreeBSD port's specific interactive configuration. It depends on the
  makefile variable <code>OPTIONS</code>. If it is present, it contains text
  representation of options available to the port in form of arguments to
  <code>dialog</code> tool, eg:
  </p>
  <pre>CPU_OPTS "Enable assembly optimizations for your CPU" off</pre>
  <p>
  This will show the ncurses based dialog (<code>dialog</code> utility), and
  allow the user to check desired options. These will be stored in a file
  in <code>/var/db/ports/</code>. This file is then affecting other <code>make</code>
  commands bellow.
  </p>
  
  <div class="phase">
  Get fetch dependencies:
  <pre class="terminal"># make -V FETCH_DEPENDS</pre>
  Fetch all archives and patches:
  <pre class="terminal"># make fetch</pre>
  </div>

  <h3>Download aka fetch</h3>
  <p>
  This phase will download all necessary archives and patches for you. It may
  happen, that a port needs additional software to download it. Therefore it
  will first install any fetch dependencies. They are defined in the
  <code>Makefile</code> in the <code>FETCH_DEPENDS</code> variable.
  After any fetch dependencies are installed, <code>make</code> downloads all
  archives defined.
  </p>
  <p>
  It is important to mention here, that while downloading, this phase heavily
  utilizes network bandwidth, but no other resources like CPU or IO. This will
  become important when optimizing the ports processing.
  </p>


  <div class="phase">
    Get extract dependencies:
    <pre class="terminal"># make -V EXTRACT_DEPENDS</pre>
    Extract all archives:
    <pre class="terminal"># make extract</pre>
    Get patch dependencies:
    <pre class="terminal"># make -V PATCH_DEPENDS</pre>
    Apply FreeBSD specific patches:
    <pre class="terminal"># make patch</pre>
  </div>
  <h3>Extraction and patching</h3>
  <p>
  There are two separate phases for extraction and patching, but they are
  very similar from the point of view of system resources. They both use mainly
  disk I/O and CPU power. Both can have it's specific requirements, that need
  to be installed before the phase.
  </p>
  <p>
  Extraction may need additional software, that is defined in the variable
  <code>EXTRACT_DEPENDS</code>.
  </p>
  <p>
  The patching phase is FreeBSD specific. It means, it will apply FreeBSD specific
  patches needed over the standard software delivery (eg. it will not compile
  on FreeBSD without it). Any patching requested by the vendor of the software
  is done in the build phase.
  </p>
  <p>
  Patching can also have dependencies required to apply the patches defined
  in <code>PATCH_DEPENDS</code>
  </p>


  <div class="phase">
    Run <code>./configure</code> script:
    <pre class="terminal"># make configure</pre>
    List build dependencies:
    <pre class="terminal"># make -V BUILD_DEPENDS</pre>
    Build the port:
    <pre class="terminal"># make</pre>
  </div>
  <h3>Building</h3>
  <p>
  The standard build process from sources takes two basic steps. The configuration
  script, that detects installed tools and libraries and many other information
  and build using any build automation tool.
  </p>
  <p>
  The first one, mostly the very well known script <code>./configure</code>
  detects and prepares configuration for the build. In oposite of the configuration
  phase mentioned earlier, this one is not interactive, and is part of the
  software delivery (same for other systems). On FreeBSD, it usually takes
  advantage of the mentioned configuration phase, and <code>./configure</code>
  parameters are generated based on the user choices made with <code>make config</code>.
  </p>
  <p>
  Building of the software may also need some additional tools or libraries
  installed. These dependencies are defined in <code>Makefile</code> in the
  variable <code>BUILD_DEPENDS</code>. So make will install them prior the actual
  build starts.
  </p>

  <div class="phase">
    List required libraries:
    <pre class="terminal"># make -V LIB_DEPENDS</pre>
    Install the port:
    <pre class="terminal"># make install</pre>
    List run dependencies:
    <pre class="terminal"># make -V RUN_DEPENDS</pre>
  </div>
  <h3>Installation</h3>
  <p>
  The installation of the software systemwide is performed in this phase. This
  means, that all required libraries must be installed on the system too, so
  first the dependencies specified in <code>LIB_DEPENDS</code> must be checked
  and installed if missing.
  </p>
  <p>
  Installation into system locations (<code>/usr/local/bin,/usr/local/lib,etc.</code>)
  is performed, and then another dependencies are checked and installed. These
  are dependencies required for the software to run.
  </p>
  <p>
  They are defined in <code>Makefile</code> in variable <code>RUN_DEPENDS</code>.
  </p>
  <p>
  One more important note for our processing is, that this dependencies might be
  cyclic (A depends on B and B depends on A). While it is checked after the
  installation, the cycle will not cause infinite recursion, but terminates
  correctly when the whole cycle is processed.
  </p>


  <div class="phase">
    Clean the port working directory and all dependencies:
    <pre class="terminal"># make clean</pre>
    Clean this port only:
    <pre class="terminal"># make do-clean</pre>
    Clean the port and remove downloaded files:
    <pre class="terminal"># make dist-clean</pre>
  </div>
  <h3>Cleanup</h3>
  <p>
  Last discussed phase is the cleanup after installation. It will remove all
  temporary files used during the installation. Extracted archives, build
  object files etc. It is important to free the disk space. Some packages may
  take gigabytes of disk space (eg. openoffice, java, etc.).
  </p>
  <p>
  When cleaning the port with all dependencies, then all dependencies encountered
  in any phase are cleaned up (<code>FETCH_DEPENDS</code>, <code>EXTRACT_DEPENDS</code>,
  <code>PATCH_DEPENDS</code>, <code>BUILD_DEPENDS</code>, <code>LIB_DEPENDS</code>
  and <code>RUN_DEPENDS</code>).
  </p>

  <h2>Simplified decomposition</h2>
    <div class="figure right" title="Port decomposition">
  <svg xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:svg="http://www.w3.org/2000/svg"
    width="306pt" height="82pt" viewBox="-5 -1 306 82" class="right"
  >
  <text class="desc" y="8">Port without configuration</text>
  <use xlink:href="#port-phases" y="10" />
  <text class="desc" y="48">Port with configuration</text>
  <use xlink:href="#port-phases-with-config" y="50" />

  <text x="199" y="8" class="desc">Resources:</text>
  <g transform="translate(199,30)"><use xlink:href="#desc-cpu"/><text x="2" y="8" class="desc">CPU</text></g>
  <!--g transform="translate(199,20)"><use xlink:href="#desc-io"/><text x="2" y="8" class="desc">Disk I/O</text></g-->
  <g transform="translate(199,20)"><use xlink:href="#desc-net"/><text x="2" y="8" class="desc">Network</text></g>
  <g transform="translate(199,10)"><use xlink:href="#desc-human"/><text x="2" y="8" class="desc">Human interaction</text></g>
  </svg>
  </div>
  <p>
  For the purposis of the parallelization and optimal resource utilization, we don't
  need the full decomposition into 8 phases as discussed before. We can group the
  phases into resource specific groups and reduce the count. Make the groups in the
  following table:
  </p>
  <table>
  <tr><td>make config</td></tr>
  <tr><td>make fetch</td></tr>
  <tr><td>make extract</td></tr>
  <tr><td>make patch</td></tr>
  <tr><td>make configure</td></tr>
  <tr><td>make</td></tr>
  <tr><td>make install</td></tr>
  <tr><td>make clean</td></tr>
  </table>

  <h2>Port dependencies</h2>
  <div class="figure" title="Port dependencies">
  <svg xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:svg="http://www.w3.org/2000/svg"
    width="330pt" height="262pt" viewBox="-40 -15 330 262" class="right"
  >
  <line x1="120" y1="5"   x2="120" y2="29"  class="trans build"/>
  <line x1="120" y1="5"   x2="240" y2="109" class="trans build"/>
  <line x1="120" y1="45"  x2="120" y2="69"  class="trans build"/>
  <line x1="120" y1="45"  x2="240" y2="109" class="trans build"/>
  <line x1="120" y1="85"  x2="240" y2="109" class="trans build"/>
  <line x1="120" y1="85"  x2="160" y2="109" class="trans lib"/>
  <line x1="120" y1="85"  x2="80"  y2="109" class="trans build"/>
  <line x1="120" y1="85"  x2="0"   y2="109" class="trans extract"/>
  <line x1="120" y1="85"  x2="160" y2="149" class="trans lib"/>
  <line x1="120" y1="85"  x2="120" y2="189" class="trans lib"/>
  <line x1="160" y1="125" x2="240" y2="149" class="trans extract"/>
  <line x1="160" y1="125" x2="160" y2="149" class="trans lib"/>
  <line x1="80"  y1="125" x2="80"  y2="149" class="trans lib"/>
  <line x1="80"  y1="125" x2="0"   y2="149" class="trans build"/>
  <line x1="80"  y1="165" x2="80"  y2="229" class="trans build"/>
  <line x1="80"  y1="165" x2="120" y2="189" class="trans lib"/>
  <line x1="120" y1="205" x2="80"  y2="229" class="trans build"/>
  <g transform="translate(120,  0)"><use xlink:href="#port"/><text class="port">gnustep-objc</text></g>
  <g transform="translate(120, 40)"><use xlink:href="#port"/><text class="port">gnustep-make</text></g>
  <g transform="translate(120, 80)"><use xlink:href="#port"/><text class="port">gcc42</text></g>
  <g transform="translate(  0,120)"><use xlink:href="#port-config"/><text class="port">perl5.10</text></g>
  <g transform="translate( 80,120)"><use xlink:href="#port"/><text class="port">bison</text></g>
  <g transform="translate(160,120)"><use xlink:href="#port"/><text class="port">mpfr</text></g>
  <g transform="translate(240,120)"><use xlink:href="#port"/><text class="port">gmake</text></g>
  <g transform="translate(  0,160)"><use xlink:href="#port-config"/><text class="port">m4</text></g>
  <g transform="translate( 80,160)"><use xlink:href="#port"/><text class="port">gettext</text></g>
  <g transform="translate(160,160)"><use xlink:href="#port-config"/><text class="port">gmp</text></g>
  <g transform="translate(240,160)"><use xlink:href="#port"/><text class="port">xz</text></g>
  <g transform="translate(120,200)"><use xlink:href="#port-config"/><text class="port">libiconv</text></g>
  <g transform="translate( 80,240)"><use xlink:href="#port"/><text class="port">libtool22</text></g>

  <text x="200" y="193" class="desc">Dependencies:</text>
  <g transform="translate(200,200)"><line x2="20" class="trans fetch"  /><text x="22" y="3" class="desc">fetch</text></g>
  <g transform="translate(200,210)"><line x2="20" class="trans extract"/><text x="22" y="3" class="desc">extract</text></g>
  <g transform="translate(200,220)"><line x2="20" class="trans patch"  /><text x="22" y="3" class="desc">patch</text></g>
  <g transform="translate(200,230)"><line x2="20" class="trans build"  /><text x="22" y="3" class="desc">build</text></g>
  <g transform="translate(200,240)"><line x2="20" class="trans lib"    /><text x="22" y="3" class="desc">lib</text></g>
  <g transform="translate(200,250)"><line x2="20" class="trans run"    /><text x="22" y="3" class="desc">run</text></g>
  </svg>
  </div>

  <div class="figure" title="Sequential processing">
  <svg xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:svg="http://www.w3.org/2000/svg"
    width="330pt" height="272pt" viewBox="-40 -15 330 272" class="right"
  >
  <line x1="110" y1="0"   x2="110" y2="40"  class="req"/>
  <line x1="110" y1="40"  x2="110" y2="80"  class="req"/>
  <line x1="110" y1="80"  x2="-30" y2="120" class="req"/>
  <line x1="-10" y1="120" x2="10"  y2="120" class="req"/>
  <line x1="30"  y1="120" x2="70"  y2="120" class="req"/>
  <line x1="70"  y1="120" x2="-30" y2="160" class="req"/>
  <line x1="-10" y1="160" x2="10"  y2="160" class="req"/>
  <line x1="30"  y1="160" x2="70"  y2="160" class="req"/>
  <line x1="70"  y1="160" x2="70"  y2="240" class="req"/>
  <line x1="70"  y1="240" x2="90"  y2="240" class="req"/>
  <line x1="110" y1="240" x2="90"  y2="200" class="req"/>
  <line x1="110" y1="200" x2="130" y2="200" class="req"/>
  <line x1="150" y1="200" x2="90"  y2="160" class="req"/>
  <line x1="110" y1="160" x2="90"  y2="120" class="req"/>
  <line x1="110" y1="120" x2="150" y2="120" class="req"/>
  <line x1="150" y1="120" x2="130" y2="160" class="req"/>
  <line x1="150" y1="160" x2="170" y2="160" class="req"/>
  <line x1="190" y1="160" x2="230" y2="160" class="req"/>
  <line x1="230" y1="160" x2="250" y2="160" class="req"/>
  <line x1="270" y1="160" x2="170" y2="120" class="req"/>
  <line x1="190" y1="120" x2="230" y2="120" class="req"/>
  <line x1="230" y1="120" x2="250" y2="120" class="req"/>
  <line x1="270" y1="120" x2="130" y2="80"  class="req"/>
  <line x1="150" y1="80"  x2="130" y2="40"  class="req"/>
  <line x1="150" y1="40"  x2="130" y2="0"   class="req"/>
  
  <g transform="translate(120,  0)"><use xlink:href="#seq-port"/><text y="-10" class="port">gnustep-objc</text></g>
  <g transform="translate(120, 40)"><use xlink:href="#seq-port"/><text y="-10" class="port">gnustep-make</text></g>
  <g transform="translate(120, 80)"><use xlink:href="#seq-port"/><text y="-10" class="port">gcc42</text></g>
  <g transform="translate(  0,120)"><use xlink:href="#seq-port-config"/><text y="-10" class="port">perl5.10</text></g>
  <g transform="translate( 80,120)"><use xlink:href="#seq-port"/><text y="-10" class="port">bison</text></g>
  <g transform="translate(160,120)"><use xlink:href="#seq-port"/><text y="-10" class="port">mpfr</text></g>
  <g transform="translate(240,120)"><use xlink:href="#seq-port"/><text y="-10" class="port">gmake</text></g>
  <g transform="translate(  0,160)"><use xlink:href="#seq-port-config"/><text y="-10" class="port">m4</text></g>
  <g transform="translate( 80,160)"><use xlink:href="#seq-port"/><text y="-10" class="port">gettext</text></g>
  <g transform="translate(160,160)"><use xlink:href="#seq-port-config"/><text y="-10" class="port">gmp</text></g>
  <g transform="translate(240,160)"><use xlink:href="#seq-port"/><text y="-10" class="port">xz</text></g>
  <g transform="translate(120,200)"><use xlink:href="#seq-port-config"/><text y="-10" class="port">libiconv</text></g>
  <g transform="translate( 80,240)"><use xlink:href="#seq-port"/><text y="-10" class="port">libtool22</text></g>
  </svg>
  </div>


  <div class="figure" title="Parallel processing">
  <svg xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:svg="http://www.w3.org/2000/svg"
    width="600pt" height="408pt" viewBox="-40 -15 600 408" class="right"
  >
  <line x1="150" y1="10" x2="150" y2="70" class="req tree"/>
  <line x1="170" y2="10" x2="170" y1="70" class="req submit"/>
  <line x1="190" y2="10" x2="190" y1="70" class="req"/>
  <line x1="150" y1="10" x2="310" y2="190" class="req tree"/>
  <line x1="330" y2="10" x2="170" y1="190" class="req submit"/>
  <line x1="350" y2="10" x2="190" y1="190" class="req"/>
  <line x1="150" y1="70" x2="150" y2="130" class="req tree"/>
  <line x1="170" y2="70" x2="170" y1="130" class="req submit"/>
  <line x1="190" y2="70" x2="190" y1="130" class="req"/>
  <line x1="150" y1="70" x2="310" y2="190" class="req tree"/>
  <line x1="330" y2="70" x2="170" y1="190" class="req submit"/>
  <line x1="350" y2="70" x2="190" y1="190" class="req"/>
  <line x1="150" y1="130" x2="230" y2="190" class="req tree"/>
  <line x1="250" y2="130" x2="170" y1="190" class="req submit"/>
  <line x1="270" y2="130" x2="190" y1="190" class="req"/>
  <line x1="150" y1="130" x2="310" y2="190" class="req tree"/>
  <line x1="330" y2="130" x2="170" y1="190" class="req submit"/>
  <line x1="350" y2="130" x2="190" y1="190" class="req"/>
  <line x1="150" y1="130" x2="70"  y2="190" class="req tree"/>
  <line x1="90"  y2="130" x2="170" y1="190" class="req submit"/>
  <line x1="110" y2="130" x2="190" y1="190" class="req"/>
  <line x1="150" y1="130" x2="-30" y2="190" class="req tree"/>
  <line x1="10"  y2="130" x2="170" y1="190" class="req submit"/>
  <line x1="30"  y2="130" x2="190" y1="190" class="req"/>
  <line x1="150" y1="130" x2="130" y2="310" class="req tree"/>
  <line x1="170" y2="130" x2="170" y1="310" class="req submit"/>
  <line x1="190" y2="130" x2="190" y1="310" class="req"/>
  <line x1="150" y1="130" x2="210" y2="250" class="req tree"/>
  <line x1="250" y2="130" x2="170" y1="250" class="req submit"/>
  <line x1="270" y2="130" x2="190" y1="250" class="req"/>
  <line x1="70" y1="190" x2="-30" y2="250" class="req tree"/>
  <line x1="10"  y2="190" x2="90" y1="250" class="req submit"/>
  <line x1="30"  y2="190" x2="110" y1="250" class="req"/>
  <line x1="70" y1="190" x2="70" y2="250" class="req tree"/>
  <line x1="90"  y2="190" x2="90" y1="250" class="req submit"/>
  <line x1="110"  y2="190" x2="110" y1="250" class="req"/>
  <line x1="230" y1="190" x2="210" y2="250" class="req tree"/>
  <line x1="250"  y2="190" x2="250" y1="250" class="req submit"/>
  <line x1="270"  y2="190" x2="270" y1="250" class="req"/>
  <line x1="230" y1="190" x2="310" y2="250" class="req tree"/>
  <line x1="330"  y2="190" x2="250" y1="250" class="req submit"/>
  <line x1="350"  y2="190" x2="270" y1="250" class="req"/>
  <line x1="70" y1="250" x2="70" y2="370" class="req tree"/>
  <line x1="90"  y2="250" x2="90" y1="370" class="req submit"/>
  <line x1="110"  y2="250" x2="110" y1="370" class="req"/>
  <line x1="70" y1="250" x2="130" y2="310" class="req tree"/>
  <line x1="170"  y2="250" x2="90" y1="310" class="req submit"/>
  <line x1="190"  y2="250" x2="110" y1="310" class="req"/>
  <line x1="150" y1="310" x2="70" y2="370" class="req tree"/>
  <line x1="90" y2="310" x2="170" y1="370" class="req submit"/>
  <line x1="110" y2="310" x2="190" y1="370" class="req"/>

  <g transform="translate(160,  0)"><use xlink:href="#par-port"/><text class="port-bg">gnustep-objc</text><text class="port">gnustep-objc</text></g>
  <g transform="translate(160, 60)"><use xlink:href="#par-port"/><text class="port-bg">gnustep-make</text><text class="port">gnustep-make</text></g>
  <g transform="translate(160,120)"><use xlink:href="#par-port"/><text class="port-bg">gcc42</text><text class="port">gcc42</text></g>
  <g transform="translate(  0,180)"><use xlink:href="#par-port-config"/><text class="port-bg">perl5.10</text><text class="port">perl5.10</text></g>
  <g transform="translate( 80,180)"><use xlink:href="#par-port"/><text class="port-bg">bison</text><text class="port">bison</text></g>
  <g transform="translate(240,180)"><use xlink:href="#par-port"/><text class="port-bg">mpfr</text><text class="port">mpfr</text></g>
  <g transform="translate(320,180)"><use xlink:href="#par-port"/><text class="port-bg">gmake</text><text class="port">gmake</text></g>
  <g transform="translate(  0,240)"><use xlink:href="#par-port-config"/><text class="port-bg">m4</text><text class="port">m4</text></g>
  <g transform="translate( 80,240)"><use xlink:href="#par-port"/><text class="port-bg">gettext</text><text class="port">gettext</text></g>
  <g transform="translate(240,240)"><use xlink:href="#par-port-config"/><text class="port-bg">gmp</text><text class="port">gmp</text></g>
  <g transform="translate(320,240)"><use xlink:href="#par-port"/><text class="port-bg">xz</text><text class="port">xz</text></g>
  <g transform="translate(160,300)"><use xlink:href="#par-port-config"/><text class="port-bg">libiconv</text><text class="port">libiconv</text></g>
  <g transform="translate( 80,360)"><use xlink:href="#par-port"/><text class="port-bg">libtool22</text><text class="port">libtool22</text></g>

  <use x="385" y="10" xlink:href="#fat-arrow"/>
  <use x="385" y="60" xlink:href="#fat-arrow"/>
  <use x="385" y="110" xlink:href="#fat-arrow"/>
  <use x="385" y="160" xlink:href="#fat-arrow"/>
  <text x="385" y="-5" class="desc">Dependency threadpool</text>
  <text x="385" y="45" class="desc">User thread</text>
  <text x="385" y="95" class="desc">Fetch threadpool</text>
  <text x="385" y="145" class="desc">Install threadpool</text>
  <use x="400" y="0" xlink:href="#queue-dep"/>
  <use x="400" y="50"  xlink:href="#queue-man"/>
  <use x="400" y="100" xlink:href="#queue-net"/>
  <use x="400" y="150" xlink:href="#queue-cpu"/>
  <use x="485" y="10" xlink:href="#fat-arrow"/>
  <use x="530" y="55" xlink:href="#thread"/>
  <use x="500" y="-10" xlink:href="#threadpool"/>
  <use x="500" y="90" xlink:href="#threadpool"/>
  <use x="500" y="140" xlink:href="#threadpool"/>

  <text x="0" y="3" class="desc">Dependencies:</text>
  <g transform="translate(0,30)"><line x2="20" class="req"/><text x="22" y="3" class="desc">finish</text></g>
  <g transform="translate(0,20)"><line x2="20" class="req submit"/><text x="22" y="3" class="desc">submit</text></g>
  <g transform="translate(0,10)"><line x2="20" class="req tree"/><text x="22" y="3" class="desc">shortest</text></g>
  </svg>
  </div>

  <h2>Configuration and parallel building of the dependency graph</h2>

  <h3>Input</h3>
  Performed in main thread
  <ol>
    <li><strong>foreach</strong> job specified on input <strong>do:</strong></li>
    <li>register job</li>
    <li>decompose it into tasks</li>
    <li><strong>if</strong> OTPIONS <strong>then</strong> submit to Configure <strong>else</strong> submit to Traverse</li>
  </ol>

  <h3>Configure</h3>
  Single configure thread with exclusive access to terminal
  <ol>
    <li>Configure port (make config)</li>
    <li>Submit to Traverse</li>
  </ol>

  <h3>Traverse</h3>
  Single traverse thread to minimize risk of simultaneous access to same job data
  <ol>
    <li><strong>foreach</strong> dependency type <strong>foreach</strong> dependency <strong>if</strong> not registered perform Input</li>
    <li>Try submit Fetch</li>
  </ol>

  <h2>Parallel processing of port tasks</h2>

  <h3>General task</h3>
  Fixed count of tasks per resource (eg. 2 threads for CPU, 4 threads for Network, 1 thread for Disk IO)
  <ol>
    <li>perform requested operation with task</li>
    <li><strong>foreach</strong> descendant notify result and try submit descendant</li>
  </ol>

</div>
<div class="footer"><small>&copy; 2010-2011 Ondrej Fischer</small></div>
</body>

</html>
